1875C - Jellyfish and Green Apple - CodeForces Solution

#include <bits/stdc++.h>
#define MAX 31624

using namespace std;

bitset<31624> primes;

vector<int> all_primes;
void siev(){
    primes.set();
    primes[0] = 0;
    primes[1] = 0;

    for(long long i = 2; i < MAX; i++)
        if(primes[i]){
            for(long long j = i * i; j < MAX; j += i)
                primes[j] = 0;
            all_primes.push_back((int)i);
        }
}
set<int> powers ;
void powers_two(){
    int i = 1;
    while (i < 1000000000){
      powers.insert(i);
      i *= 2;
    }
    
}

int main(){
  siev();
  powers_two();

  int t, n, m, nc, mc, ans;cin >> t;
  bool prime, possible;
  for(int tt = 0; tt< t; tt++){
    cin >> n; cin >> m;
    nc = n; mc = m;
    if(n % m == 0){
      ans = 0;
      cout << ans << endl;
      continue;
    }
    prime = true;
    possible = true;
    while (n % 2 == 0){
      n /= 2;
    }
    while (m % 2 == 0){
      m /= 2;
    }
    if(n % m) {
      cout << -1 << endl;
    }
    else{
      long long cont = 0;
      while (nc % mc){
        //cout << nc << endl;
        nc %= mc;
        cont += nc;
        nc *= 2;
      }
      cout << cont << endl; 
    }
  }
}